package tree;

public class rbTree {
    public static void main(String[] args) {
        rbTree rbtree = new rbTree();
        int[] arr = {4, 2, 6, 1, 3, 5, 15, 7, 16,14};
        for (int i = 0; i < arr.length; i++) {
            rbtree.insert(arr[i]);
        }
        System.out.println(isRBTree(root));
        inOrder(root);
    }
    static class rbTreeNode {
        public int val;
        public rbTreeNode left;
        public rbTreeNode right;
        public rbTreeNode parent;
        public Color color;

        public rbTreeNode(int val) {
            this.val = val;
            this.color = Color.Red;
        }
    }

    static rbTreeNode root;

    public static boolean insert(int val) {
        rbTreeNode node = new rbTreeNode(val);
        if (root == null) {
            root = node;
            root.color = Color.Black;
            return true;
        }
        rbTreeNode cur = root;
        rbTreeNode prev = null;
        while (cur != null) {
            prev = cur;
            if (cur.val > val) {
                cur = cur.left;
            } else if (cur.val < val) {
                cur = cur.right;
            } else {
                System.out.println("已存在,无法存入");
                return false;
            }
        }
        if (val > prev.val) {
            prev.right = node;
        } else {
            prev.left = node;
        }
        node.parent = prev;
        cur = node;

        //进行颜色调整
        while (prev != null && prev.color == Color.Red) {
            //prev节点是红色,必存在祖父节点
            rbTreeNode grandfather = prev.parent;
            if (prev == grandfather.left) {
                rbTreeNode uncle = grandfather.right;
                if (uncle != null && uncle.color == Color.Red) {
                    prev.color = Color.Black;
                    uncle.color = Color.Black;
                    grandfather.color = Color.Red;
                    cur = grandfather;
                    prev = cur.parent;
                } else {
                    //叔叔节点为空或者叔叔节点的颜色是黑色
                    //右旋
                    if (cur == prev.right) {
                        left(prev);
                        rbTreeNode tmp = cur;
                        cur = prev;
                        prev = tmp;
                    }
                    right(grandfather);
                    grandfather.color = Color.Red;
                    prev.color = Color.Black;
                }
            } else {
                rbTreeNode uncle = grandfather.left;
                if (uncle != null && uncle.color == Color.Red) {
                    prev.color = Color.Black;
                    uncle.color = Color.Black;
                    grandfather.color = Color.Red;
                    cur = grandfather;
                    prev = cur.parent;
                } else {
                    //叔叔节点为空或者叔叔节点的颜色是黑色
                    //右旋
                    if (cur == prev.left) {
                        right(prev);
                        rbTreeNode tmp = cur;
                        cur = prev;
                        prev = tmp;
                    }
                    left(grandfather);
                    grandfather.color = Color.Red;
                    prev.color = Color.Black;
                }
            }
        }
        root.color = Color.Black;
        return true;
    }
    public static void inOrder(rbTreeNode root) {
        if(root==null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    private static void left(rbTreeNode node) {
        rbTreeNode Rnode = node.right;
        rbTreeNode RLnode = Rnode.left;
        rbTreeNode pPnode = node.parent;
        Rnode.left = node;
        node.right = RLnode;
        node.parent = Rnode;
        if (RLnode != null) {
            RLnode.parent = node;
        }
        //是不是根结点
        if (node == root) {
            //是根节点
            root = Rnode;
            Rnode.parent = null;
        } else {
            if (pPnode.left == node) {
                pPnode.left = Rnode;
            } else {
                pPnode.right = Rnode;
            }
            Rnode.parent = pPnode;
        }
    }

    private static void right(rbTreeNode node) {
        rbTreeNode Lnode = node.left;
        rbTreeNode LRnode = Lnode.right;
        rbTreeNode pPnode = node.parent;
        Lnode.right = node;
        node.left = LRnode;
        node.parent = Lnode;
        if (LRnode != null) {
            LRnode.parent = node;
        }
        //是不是根结点
        if (node == root) {
            //是根节点
            root = Lnode;
            Lnode.parent = null;
        } else {
            if (pPnode.left == node) {
                pPnode.left = Lnode;
            } else {
                pPnode.right = Lnode;
            }
            Lnode.parent = pPnode;
        }
    }

    public static boolean isRBTree(rbTreeNode root) {
        if (root == null) {
            return true;
        }
        if(root.color!=Color.Black) {
            System.out.println("违反性质: 根结点的颜色是黑色");
            return false;
        }
        //判断是否存在连续红色节点,可以根据每个红色节点是否有父红色节点来判断
        if (!isRed(root)) {
            System.out.println("违法了性质: 红黑树不存在两个连续的红色节点");
            return false;
        }

        int blacknum = 0;
        rbTreeNode cur = root;
        while (cur != null) {
            if (cur.color == Color.Black) {
                blacknum++;
            }
            cur = cur.left;
        }
        int pathnum = 0;
        if (!blackNum(root, blacknum, pathnum)) {
            System.out.println("违反性质: 每条路径的黑色节点数目相同");
            return false;
        }
        return true;
    }

    private static boolean blackNum(rbTreeNode root, int blacknum, int pathnum) {
        if (root == null) {
            return true;
        }
        if (root.color == Color.Black) {
            pathnum++;
        }
        if (root.left == null && root.right == null ) {
            if(pathnum != blacknum) {
                System.out.println(root.val);
                return false;
            }
        }
        return blackNum(root.left, blacknum, pathnum) && blackNum(root.right, blacknum, pathnum);
    }

    private static boolean isRed(rbTreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.color == Color.Red && root.parent.color == Color.Red) {
            return false;
        }
        return isRed(root.left) && isRed(root.right);
    }

}